package com.jacklei.ch18;

import java.util.*;

/*
* 给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

 

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
 

提示：

1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
通过次数32,398提交次数73,903

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bus-routes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class BusRoutes {
    public static void main(String[] args) {
        BusRoutes b = new BusRoutes();
       System.out.println(b.numBusesToDestination(new int[][]{
//                {25,33},//0
//                {3,5,13,22,23,29,37,45,49},//1
//                {15,16,41,47},//2
//                {5,11,17,23,33},//3
//                {10,11,12,29,30,39,45},//4
//                {2,5,23,24,33},//5
//                {1,2,9,19,20,21,23,32,34,44},//6
//                {7,18,23,24},//7
//                {1,2,7,27,36,44},//8
//                {7,14,33}//9
//                /*
//                * start : 9 8 7
//                * stop: 2
//                * */
               /*
               * [[0,1,6,16,22,23],[14,15,24,32],[4,10,12,20,24,28,33],[1,10,11,19,27,33],[11,23,25,28],[15,20,21,23,29],[29]]
4
21*/
        {0,1,6,16,22,23},
        {14,15,24,32},
        {4,10,12,20,24,28,33},
        {1,10,11,19,27,33},
        {11,23,25,28},
        {15,20,21,23,29},
        {29}
        }, 4, 21));
    }

    class Bus{
        int BusNum;
        int value[];
        Set<Bus> next = new HashSet<>();

        public Bus(int busNum) {
            BusNum = busNum;
        }
    }
    public int numBusesToDestination(int[][] routes, int source, int target) {
        HashMap<Integer,Bus> map = new HashMap<>();
        HashSet<Integer> startBus = new HashSet<>();
        HashSet<Integer> stopBus = new HashSet<>();
        for (int i = 0; i < routes.length; i++) {
            Bus bus = new Bus(i);
            bus.value = routes[i];
            map.put(i,bus);
        }
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                if (routes[i][j] == target) stopBus.add(i);
                if (routes[i][j] == source) startBus.add(i);
                for (Map.Entry<Integer, Bus> integerBusEntry : map.entrySet()) {
                    if(integerBusEntry.getKey() != routes[i][j])
                    for (int k = 0; k < integerBusEntry.getValue().value.length; k++) {
                        if(integerBusEntry.getValue().value[k] == routes[i][j]){
                            Bus bus = map.get(i);
                            bus.next.add(integerBusEntry.getValue());
                            integerBusEntry.getValue().next.add(bus);
                        }
                    }
                }
            }
        }

        int res = 0;
        int resMax = map.size();
        boolean[] flat = new boolean[resMax];
        //广度遍历

        Queue<Bus> queue = new LinkedList<>();

        for (Integer bus1 : startBus) {
            Bus bus = map.get(bus1);
            queue.offer(bus);
            flat[bus.BusNum] = true;
        }



        while (!queue.isEmpty()){
            res++;
            for (int i = 0; i < queue.size(); i++) {
                Bus poll = queue.poll();
                if(stopBus.contains(poll.BusNum)) return res;
                for (Bus bus1 : poll.next) {
                    if(!flat[bus1.BusNum]){
                        queue.offer(bus1);
                        flat[bus1.BusNum] = true;
                    }
                }
            }
        }
        return -1;

    }


        public int numBusesToDestination1(int[][] routes, int source, int target) {
            if (source == target) {
                return 0;
            }

            int n = routes.length;
            boolean[][] edge = new boolean[n][n];
            Map<Integer, List<Integer>> rec = new HashMap<Integer, List<Integer>>();
            for (int i = 0; i < n; i++) {
                for (int site : routes[i]) {
                    List<Integer> list = rec.getOrDefault(site, new ArrayList<Integer>());
                    for (int j : list) {
                        edge[i][j] = edge[j][i] = true;
                    }
                    list.add(i);
                    rec.put(site, list);
                }
            }

            int[] dis = new int[n];
            Arrays.fill(dis, -1);
            Queue<Integer> que = new LinkedList<Integer>();
            for (int bus : rec.getOrDefault(source, new ArrayList<Integer>())) {
                dis[bus] = 1;
                que.offer(bus);
            }
            while (!que.isEmpty()) {
                int x = que.poll();
                for (int y = 0; y < n; y++) {
                    if (edge[x][y] && dis[y] == -1) {
                        dis[y] = dis[x] + 1;
                        que.offer(y);
                    }
                }
            }

            int ret = Integer.MAX_VALUE;
            for (int bus : rec.getOrDefault(target, new ArrayList<Integer>())) {
                if (dis[bus] != -1) {
                    ret = Math.min(ret, dis[bus]);
                }
            }
            return ret == Integer.MAX_VALUE ? -1 : ret;
        }
    }



